/*

--1--
快速排序
void quick_sort(int* arr,int start,int end)
{
    if(arr==nullptr||start>=end||start<0)
        return;
    int temp=arr[start];
    int i=start;
    int j=end;
    while(i<j)
    {
        while(i<j&&arr[j]>=temp)
            j--;
        arr[i]=arr[j];
        while(i<j&&arr[i]<=temp)
            i++;
        arr[j]=arr[i];
    }
    arr[j]=temp;
    quick_sort(arr,start,i-1);
    quick_sort(arr,j+1,end);
}

void quick_sort(int* arr,int start,int end)
{
    if(arr==nullptr||start>=end||start<0)
        return;
    int small=start;
    swap(&arr[start],&arr[end]);
    for(int i=start;i<=end-start;i++)
    {
        if(arr[i]<arr[end])
        {
            if(i!=small)
                swap(arr[small],arr[i]);
            small++;
        }
    }
    swap(&arr[small],&arr[end]);
    quick_sort(arr,start,small-1);
    quick_sort(arr,small+1,end);
}

//栈代替递归函数栈
void quick_sort(int* arr,int start,int end)
{
    if(arr==nullptr||start>=end||start<0)
        return;
    stack<int>sk;
    int temp=0;
    sk.push(end);
    sk.push(start);
    while(!sk.empty())
    {
        int left=sk.top(),i=left;
        sk.pop();
        int right=sk.top(),j=right;
        sk.pop();
        temp=arr[i];
        while(i<j)
        {
            while(arr[j]>temp&&i<j)
                j--;
            arr[i]=arr[j];
            while(arr[i]<temp&&i<j)
                i++;
            arr[j]=arr[i];
        }
        arr[i]=temp;
        if(right-j>1)
        {
            sk.push(right);
            sk.push(j+1);
        }
        if(i-left>1)
        {
            sk.push(i-1);
            sk.push(left);
        } 
    }
}

--2--
冒泡排序
void bubble_sort(int* arr,int size)
{
   if(arr==nullptr||size<=1)
       return;
   for(int i=size-1;i>0;i--)
        for(int j=0;j<i;j++)
            if(arr[j]>arr[j+1])
                swap(arr[j],arr[j+1]);
}


--3--
插入排序
void Insertion_sort(int* arr,int size)
{
    if(arr==nullptr||size<2)
        return;
    for(int i=1;i<size;i++)
    {
        int temp=arr[i];
        int j=i-1;
        while(j>=0&&arr[j]>temp)
        {
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=temp;
    }
}

--4--
希尔排序
void shells_sort(int* arr,int size)
{
    if(arr==nullptr||size<2)
        return;
	int i, j, gap;
	for(gap=size/3+1;gap>1;gap=gap/3+1)
	{
		for(i=0;i<gap;i++)
		{
			for(j=i+gap;j<size;j=j+gap)
			{
				if(arr[j]<arr[j-gap])
				{
					int temp=arr[j];
					int k=j-gap;
					while(k>=0&&temp<arr[k])
					{
						arr[k+gap]=arr[k];
						k=k-gap;
					}
					arr[k+gap]=temp;
				}
			}
		}
	}
}


--5--
选择排序
void selection_sort(int* arr,int size)
{
    if(arr==nullptr||size<2)
        return;
    int min;
    int tmp;
    for(int i=0;i<size-1;i++)
    {
        min=arr[i];
        tmp=i;
        for(int j=i+1;j<size;j++)
        {
            if(arr[j]<min)
            {
                tmp=j;
                min=arr[j];
            }
        }
        arr[tmp]=arr[i];
        arr[i]=min;
    }
}


--6--
桶排序
void bucket_sort(int* arr,int size)
{
    if(arr==nullptr||size<2)
        return;
    int len=100;
    int arrs[len];
    for(int i=0;i<len;i++)
        arrs[i]=-1;
    for(int i=0;i<size;i++)
        arrs[arr[i]]++;
    for(int i=0,j=0;i<len;i++)
    {
        while(arrs[i]>=0)
        {
            arr[j++]=i;
            arrs[i]--;
        }
    }
}


--7--
堆排序
void down_adjust(int* arr,int parents,int size)
{
    int node=parents;
    int tmp=0;
    int lchild=parents*2+1;
    int rchild=parents*2+2;
    if(lchild<size&&arr[lchild]>arr[node])
        node=lchild;
    if(rchild<size&&arr[rchild]>arr[node])
        node=rchild;
    if(node!=parents)
    {
        tmp=arr[parents];
        arr[parents]=arr[node];
        arr[node]=tmp;
        down_adjust(arr,node,size);
    }
}

void heap_sort(int* arr,int size)
{
    if(arr==nullptr||size<2)
        return;
    int tmp=0;
    for(int i=(size-1)/2;i>=0;i--)
        down_adjust(arr,i,size);
    for(int i=size-1;i>=0;i--)
    {
        tmp=arr[0];
        arr[0]=arr[i];
        arr[i]=tmp;
        down_adjust(arr,0,i);
    }
}

*/



/*
--1--
顺序查找
int order_find(int* arr,int size,int find)
{
    if(arr==nullptr||size<=0)
        return -1;
    for(int i=0;i<size;i++)
    {
        if(arr[i]==find)
            return i;
    }
    return -1;
}

--2--
二分查找
int binary_find(int* arr,int size,int find)
{
    if(arr==nullptr||size<=0)
        return -1;
    int left=0;
    int right=size-1;
    int middle=0;
    while(left<=right)
    {
        middle=(right+left)/2;
        if(arr[middle]==find)
            return middle;
        if(arr[middle]>find)
            right=middle-1;
        else
            left=middle+1;
    }
    return -1;
}

*/